package demo1;

/**
 * 斐波那契数列模型
 *      解码方法 91
 */
public class test4 {
    public int numDecodings(String s) {
        int n = s.length();
        char[] str = s.toCharArray();
        int[] dp = new int[n];
        // 初始化
        if(str[0] != '0'){
            dp[0] = 1;
        }
        // 处理边界情况
        if(n == 1){
            return dp[0];
        }
        // 初始化第二个位置
        if(str[1] != '0' && str[0] != '0'){
            dp[1] += 1;
        }
        int t = (str[0] - '0')*10 + str[1] - '0';
        if(t >= 10 && t <= 26){
            dp[1] += 1;
        }
        for(int i = 2; i < n; i++){
            // 第一个位置可以单独编码
            if(str[i] != '0'){
                dp[i] += dp[i - 1];
            }
            // i和 i-1 位置可以编码
            int tt = (str[i-1] - '0')*10 + str[i] - '0';
            if(tt >= 10 && tt <= 26){
                dp[i] += dp[i - 2];
            }
        }
        return dp[n-1];
    }

    // 使用虚拟节点
    public int numDecodings2(String s) {

        int n = s.length();
        char[] str = s.toCharArray();
        int[] dp = new int[n+1];

        dp[0] = 1; // 虚拟节点
        if(str[1 - 1] != '0'){
            dp[1] = 1;
        }

        for(int i = 2; i <= n; i++){
            // 第一个位置可以单独编码
            if(str[i-1] != '0'){
                dp[i] += dp[i - 1];
            }
            // i和 i-1 位置可以编码
            int tt = (str[i-2] - '0')*10 + str[i-1] - '0';
            if(tt >= 10 && tt <= 26){
                dp[i] += dp[i - 2];
            }
        }
        return dp[n];
    }
}

